static unordered_map<char, string> book = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
    {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
    {'8', "tuv"}, {'9', "wxyz"}
};
class Solution {
public:

    void dfs(vector<string>& res, string& digits, string& sol, int cur, int n) {
        if (cur == n) {
            res.push_back(sol);
            return;
        }

        string clist = book[digits[cur]];
        for (int i = 0; i < clist.size(); i++) {
            sol += clist[i];
            dfs(res, digits, sol, cur + 1, n);
            sol.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string sol;
        if (digits.empty()) return res;
        dfs(res, digits, sol, 0, digits.size());
        return res;
    }
};
